/*
 * (C) Copyright 2014-2018, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import org.jheaps.Heap
import org.junit.Assert
import org.junit.Test
import java.util.*

class DoubleRadixHeapTest {
    /*
	 * Affects version 0.7 of the library.
	 */
    @Test
    fun testBug1() {
        val h: Heap<Double> = DoubleRadixHeap(0.0, 3.667944409236726)
        h.insert(0.0)
        Assert.assertEquals(0.0, h.findMin(), 1e-9)
        h.insert(0.9169861023091815)
        h.deleteMin()
        Assert.assertEquals(0.9169861023091815, h.findMin(), 1e-9)
        h.insert(1.7814708581727154)
        h.deleteMin()
        Assert.assertEquals(1.7814708581727154, h.findMin(), 1e-9)
    }

    @Test
    fun testBug2() {
        val h: Heap<Double> = DoubleRadixHeap(0.0, 100.0)
        h.insert(0.0)
        Assert.assertEquals(0.0, h.findMin(), 1e-9)
        Assert.assertEquals(0.0, h.deleteMin(), 1e-9)
        h.insert(15.0)
        Assert.assertEquals(15.0, h.findMin(), 1e-9)
    }

    @Test
    fun testVerySmall() {
        val h: Heap<Double> = DoubleRadixHeap(15.0, 50.5)

        h.insert(15.3)
        h.insert(50.4)
        h.insert(20.999999)
        h.insert(50.5)
        h.insert(30.3)
        h.insert(25.2)
        h.insert(17.7777)

        Assert.assertEquals(7, h.size())
        Assert.assertEquals(15.3, h.findMin(), 1e-9)
        Assert.assertEquals(7, h.size())
        Assert.assertEquals(15.3, h.deleteMin(), 1e-9)
        Assert.assertEquals(6, h.size())
        Assert.assertEquals(17.7777, h.findMin(), 1e-9)
        Assert.assertEquals(17.7777, h.deleteMin(), 1e-9)
        Assert.assertEquals(20.999999, h.findMin(), 1e-9)
        Assert.assertEquals(20.999999, h.deleteMin(), 1e-9)
        Assert.assertEquals(25.2, h.findMin(), 1e-9)
        Assert.assertEquals(25.2, h.deleteMin(), 1e-9)
        Assert.assertEquals(30.3, h.findMin(), 1e-9)
        Assert.assertEquals(30.3, h.deleteMin(), 1e-9)
        Assert.assertEquals(50.4, h.findMin(), 1e-9)
        Assert.assertEquals(50.4, h.deleteMin(), 1e-9)
        Assert.assertEquals(50.5, h.findMin(), 1e-9)
        Assert.assertEquals(50.5, h.deleteMin(), 1e-9)
        Assert.assertEquals(h.size(), 0)
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun test() {
        val h: Heap<Double> = DoubleRadixHeap(0.0, SIZE.toDouble())

        for (i in 0 until SIZE) {
            h.insert(i.toDouble())
            Assert.assertEquals(0.0, h.findMin(), 1e-9)
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }

        for (i in SIZE - 1 downTo 0) {
            Assert.assertEquals((SIZE - i - 1).toDouble(), h.findMin(), 1e-9)
            h.deleteMin()
        }
    }

    @Test
    fun testSortRandomSeed1() {
        val h: Heap<Double> = DoubleRadixHeap(0.0, 1.0)

        val generator = Random(1)

        h.insert(0.0)
        for (i in 1 until SIZE) {
            val d = generator.nextDouble()
            h.insert(d)
        }

        var prev: Double? = null
        var cur: Double
        while (!h.isEmpty) {
            cur = h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSortRandomSeed2() {
        val h: Heap<Double> = DoubleRadixHeap(0.0, 1.0)

        val generator = Random(2)

        h.insert(0.0)
        for (i in 1 until SIZE) {
            val d = generator.nextDouble()
            h.insert(d)
        }

        var prev: Double? = null
        var cur: Double
        while (!h.isEmpty) {
            cur = h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSameMinMax() {
        val h: Heap<Double> = DoubleRadixHeap(1.0, 1.0)

        for (i in 0..14) {
            h.insert(1.0)
        }

        Assert.assertEquals(15, h.size())
        for (i in 0..14) {
            Assert.assertEquals(1.0, h.deleteMin(), 1e-9)
        }
        Assert.assertEquals(0, h.size())
    }

    @Test
    fun testMultipleDeleteMin() {
        val step = 0.3333
        val max = 1000.0

        val h: Heap<Double> = DoubleRadixHeap(0.0, max)

        h.insert(0.0)
        var cur = 0.0
        while (cur < max) {
            Assert.assertEquals(cur, h.findMin(), 1e-9)
            if (cur + step >= max) {
                break
            }
            val newCur = cur + step
            h.insert(newCur)
            Assert.assertEquals(cur, h.findMin(), 1e-9)
            Assert.assertEquals(cur, h.deleteMin(), 1e-9)
            cur = newCur
        }
    }

    @Test
    fun testMaxDifference() {
        val h: Heap<Double> = DoubleRadixHeap(0.0, Double.MAX_VALUE)

        h.insert(0.0)
        h.insert(Double.MAX_VALUE)

        Assert.assertEquals(2, h.size())
        Assert.assertEquals(0.0, h.deleteMin(), 1e-9)
        Assert.assertEquals(Double.MAX_VALUE, h.deleteMin(), 1e-9)
        Assert.assertEquals(0, h.size())
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction1() {
        DoubleRadixHeap(-1.0, Double.MAX_VALUE)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction2() {
        DoubleRadixHeap(Double.NEGATIVE_INFINITY, Double.MAX_VALUE)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction3() {
        DoubleRadixHeap(0.0, Double.POSITIVE_INFINITY)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction4() {
        DoubleRadixHeap(15.0, 14.0)
    }

    companion object {
        private const val SIZE = 100000
    }
}
